package DoublePointer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

// Lettcode 524: https://leetcode-cn.com/problems/longest-word-in-dictionary-through-deleting/
public class findLongestWord {
    public static void main(String[] args) {
        String s = "bab";
        List<String> d = Arrays.asList(new String[]{"ba","ab","a","b"});
        String t = "monkey";
        System.out.println(new findLongestWord().findLongestWord(s, d));
//        System.out.println(new findLongestWord().isValid("bab", "ba"));
    }

    public String findLongestWord(String s, List<String> d) {
        int lengthMax = -1;
        String res = "";
        for (String temp: d) {
            if (isValid(s, temp) && temp.length() >= lengthMax) {
                if (res == null || temp.length() > lengthMax) {
                    res = temp;
                    lengthMax = res.length();
                }
                if (temp.length() == lengthMax) {
                    if (temp.compareTo(res) < 0) res = temp;
                }
            }
        }
        return res;
    }

    /*
        判断是否是能够通过s得到target
     */
    public boolean isValid(String s, String target) {
        int pointS = 0;
        int pointTar = 0;
        int lengthS = s.length();
        int lengthTarget = target.length();
        if (lengthS < lengthTarget) return false;
        while (pointS < lengthS && pointTar < lengthTarget) {
            if (s.charAt(pointS) == target.charAt(pointTar)) {
                if (pointTar == lengthTarget - 1) return true;
                pointS++;
                pointTar++;
            } else {
                if (pointS == lengthS - 1) return false;
                pointS++;
            }
        }
        return false;
    }
}
